CSE 311: Homework 4 Part 2

Due: Monday, May 11th by 6:00 PM

Instructions

Write up carefully argued solutions to the following problems. Each solution should be clear enough that it can explain (to someone who does not already understand the answer) why it works. However, you may use results from lecture, the reference sheets, and previous homework without proof.

You are required to submit your own solutions. You are allowed to discuss the homework with other students. However, the write up must clearly be your own, and moreover, you must be able to explain your solution at any time. We reserve ourselves the right to ask you to explain your work at any time in the course of this class.

You have a total of three late days during the quarter, but you can only use one late day on any one homework, giving an additional day on both parts. Please plan ahead.

Submit your solution via Gradescope. In particular:

• Each numbered task should be solved on its own page (or pages). Do not write your name on the individual pages. (Gradescope will handle that.)

• When you upload your pages, make sure each one is properly rotated. If not, you can use the Gradescope controls to turn them to the proper orientation.

• Follow the Gradescope prompt to link tasks to pages.

• You are not required to typeset your solution, but your submission must be legible. It is your responsibility to make sure solutions are readable — we will not grade unreadable write-ups.

Task 1 – Keeping Up With the Cartesians

Let $A$, $B$, and $C$ be sets. Consider the following claim: $$B \times A \subseteq C \times B$$

1. Suppose that $A = \{1\}$, $B = \{1, 2\}$, and $C = \{1,2,3\}$.

   Calculate the values of the sets $B \times A$ and $C \times B$. Check whether the claim holds.

2. Suppose that $A = \{1, 2\}$, $B = \{1\}$, and $C = \{1, 2, 3\}$.

   Calculate the values of the sets $B \times A$ and $C \times B$. Check whether the claim holds.

3. Write an English proof that the claim holds given that $A \subseteq B$ and $B \subseteq C$.

   (This updated claim describes the situation in part (a) but not part (b).)

   Follow the structure of our template for subset proofs.

   Note: even though we want you to write your proof directly in English, it must still look like the translation of a formal proof. In particular, you must include all steps that would be required of a formal proof, excepting only those that we have explicitly said are okay to skip in English proofs.

Task 2 – Our Finest Power

Let $A$, $B$, and $C$ be sets. Consider the following claim: $$\mathcal{P}(A \cap (B \cup C)) \subseteq \mathcal{P}(A \cap B) \cup \mathcal{P}(A \cap C)$$

1. Suppose that $A = \{1, 2\}$, $B = \{1, 3\}$, and $C = \{2, 4\}$.

   Calculate the values of the sets $\mathcal{P}(A \cap (B \cup C))$ and $\mathcal{P}(A \cap B) \cup \mathcal{P}(A \cap C))$. Check whether the claim holds.

2. Suppose that $A = \{1\}$, $B = \{1, 2\}$, and $C = \{1, 3\}$.

   Calculate the values of the sets $\mathcal{P}(A \cap (B \cup C))$ and $\mathcal{P}(A \cap B) \cup \mathcal{P}(A \cap C))$. Check whether the claim holds.

3. Write an English proof that the claim holds given $(A \cap B) \subseteq (A \cap C)$ holds.

   (This updated claim describes the situation in part (b) but not part (a). The claim holds when either $(A \cap B) \subseteq (A \cap C)$ or $(A \cap C) \subseteq (A \cap B)$ hold, but the proof is the same for both cases thus one was omitted. Think about why that would intuitively make sense!)

   Follow the structure of our template for subset proofs.

   In your proof, you are free to use (cite or apply) the following theorems about sets:

   $$\text{Transitivity of Subset:}\ \ \ \forall A\, \forall B\, \forall C\, (((A \subseteq B) \wedge (B \subseteq C)) \to (A \subseteq C))$$

   $$\text{Distributivity of Set:}\ \ \ \forall A\, \forall B\, \forall C\, (A \cap (B \cup C) = (A \cap B) \cup (A \cap C))$$

   Note: even though we want you to write your proof directly in English, it must still look like the translation of a formal proof. In particular, you must include all steps that would be required of a formal proof, excepting only those that we have explicitly said are okay to skip in English proofs.

Task 3 – Parmesan, Romano, and Meta

Let $A$, $B$, and $C$ be sets. For each of the following claims:

1. State whether the the claim is true or false.

2. If the claim is true, write an English proof that the claim holds following the Meta Theorem template. (In your equivalence chain, you can skip steps showing commutativity or associativity, as long as each step is easy to follow.)

3. If it the claim false, give a counterexample. Provide specific finite sets for $A$, $B$, and $C$, and then calculate the value of each side of the claim, showing that they do not produce the same set. (Be sure to show the value of each intermediate expression, when calculating each side.)

1. $(A \cap B) \cup (A \cap \overline{B}) = A$

2. $(A \cup B) \,\setminus\, C = (A \cup C) \,\setminus\, B$

3. $A \,\setminus\, (B \cap C) = (A \,\setminus\, B) \cup (A \,\setminus\, C)$

Task 4 – Optional Practice Problems (Extra Credit)

The following problems are optional and do not need to be submitted. However, you may submit solutions and receive a small amount of extra credit for any 5 (of the 12) subparts, graded solely on completion. For the maximum extra credit score, at least 5 subparts should be submitted, including at least one subpart from each of the three sections.

1. Prove each of the following claims.

   1. Let $A$ and $B$ be sets. If $\mathcal{P}(A) \subseteq \mathcal{P}(B)$, then $A \subseteq B$.

   2. Let $A$ and $B$ be sets. $\mathcal{P}(A\cup B)\supseteq\mathcal{P}(A)\cup\mathcal{P}(B)$.

   3. Let $A$ and $B$ be sets. If $A\subseteq B$, then $A\times B\subseteq B\times B$.

   4. Let $A$ and $B$ be sets. If $A \neq \emptyset$ and $B \neq \emptyset$ and $A \neq B$, then $A\times B \neq B\times A$.

   5. For any set $A$ and any $n \in \mathbb{N}$, if $A$ has $n$ elements, then $\mathcal{P}(A)$ has $2^n$ elements.

      Hint: Use induction. You can use without justification the following fact: If $A$ is nonempty with $n$ elements and $x$ is an element of $A$, then $A \,\setminus\, \{x\}$ has $n-1$ elements.

2. Let $A$, $B$, and $C$ be sets. For each of the following claims, either provide an English proof that the claim holds, or give a counterexample showing that the claim does not hold.

   1. $A\setminus(B\cap C) = (A\setminus B)\cap(A\setminus C)$.

   2. $A\cap B = A\,\setminus\,(A\,\setminus\, B)$.

   3. $((A\cap \overline{A})\cup \overline{B}) \cup \overline{C} = \overline{B\cap C}$.

3. Use structural induction for the following problems. Let double be a function on lists and leaves be a function on trees, defined as follows: $$\begin{aligned} \text{double}(\mathop{\mathrm{\textsf{nil}}}) := \mathop{\mathrm{\textsf{nil}}}, &\quad \text{double}(a :: L) := a :: a :: \text{double}(L) \\ \text{leaves}(\bullet) := 1, &\quad \text{leaves}(\mathop{\mathrm{\textsf{Tree}}}(L,R)) := \text{leaves}(L) + \text{leaves}(R) \end{aligned}$$

   1. Prove $\forall L \in \textbf{List}\,(\mathop{\mathrm{\textsf{len}}}(\text{double}(L)) = 2 \cdot \mathop{\mathrm{\textsf{len}}}(L))$.

   2. Prove $\forall L \in \textbf{List}\,(\mathop{\mathrm{\textsf{positives}}}(\text{double}(L)) = 2 \cdot \mathop{\mathrm{\textsf{positives}}}(L))$.

   3. Prove $\forall T \in \textbf{Tree}\,(\text{leaves}(T) \geq \mathop{\mathrm{\textsf{height}}}(T) + 1)$.

   4. Prove $\forall T \in \textbf{Tree}\,(\text{leaves}(T) \leq 2^{\mathop{\mathrm{\textsf{height}}}(T)})$.